from typing import Optional
"""
    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
"""

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    """
    这里可以优化，用两个相距 n - 1 的指针，然后一起往后走，当后面的指针走到最后一个节点的时候，
    前面的指针刚好指向倒数第 n 个节点。
    """
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head.next is None:
            return None
        length = 0
        tem = head
        while tem:
            length += 1
            tem = tem.next
        tem1 = head
        if length - n == 0:
            return head.next
        for i in range(length - n - 1):
            tem1 = tem1.next
        tem1.next = tem1.next.next
        return head